In providing three-dimensional representations of images on a two-dimensional display means, such as a raster display screen of a cathode ray tube, for example, it is necessary to provide mechanisms for eliminating hidden surfaces and for shading visible surfaces in the image so that a general three-dimensional representational effect will be provided. In conventional display systems for producing such an effect, each point on the overall image to be displayed is created at a first processor (normally referred to as a "host" processor) but the data representing each such point is not supplied for display on the raster display screen until every point forming the overall image has been created and the data defining such complete image has been formed and stored at the host processor. The data is then supplied to a second processor (normally referred to as a local "display" processor) which is associated with the raster display means and which converts the overall point data into video data for providing a line-by-line scan display of the image to be represented.
In such systems the host processor normally performs a number of functions. The host processor provides for "viewing transformation", that is, the transforming of input information received from a data base and representing the geometry of the image to be displayed into data which provides for an appropriate scaling of the image or for a rotational movement of the image, or for an enlargement of different regions of the image. The host processor further provides for a "volume clipping" operation, i.e., determining a selected region of an overall image which is required to be displayed, a process sometimes referred to as "windowing".
Although many approaches have been used in the art to provide three-dimensional displays and which use various techniques for solving "hidden surface" and "shading" problems, one known approach has been to use a depth buffer, sometimes referred to as a Z-buffer in the system.
In such a system the host processor provides suitable information for permitting "hidden surface" or "hidden line" removal, i.e., data which defines the depth relationships among the points which form the image so that points on one portion of the image which are behind points on other portions of the image at the same display location in the overall visual representation are effectively removed, i.e. not used, in the displayed image. Such depth information is normally stored in the host processor as an array of data points in a suitable portion (The depth buffer portion) of the processor memory.
The host computer also performs the function of shading visible surfaces of the image, i.e., it creates suitable intensity values for each visible point on the overall image so as to provide a three-dimensional shading effect in the image display.
The host processor further provides for "scan conversion" or "rasterization" of the data so that the data is translated into the necessary data for making up the image needed at the display means in terms of the color and intensity, as well as the locations, of all of the points which form the image. Such data is then supplied from the host processor to the display processor for display on a cathode tube screen, for example, on a line-by-line basis.
When a depth, or Z, buffer approach is used, the hidden surface removal problem is solved at the host processor by the use of a suitable algorithm, sometimes referred to as a depth buffer or Z-buffer algorithm, which processes the input data and stores the necessary depth relationship information required to determine each visible point of the three-dimensional image, such processed depth information being stored in the depth buffer portion of memory. Data defining the location, color and intensity of each point of the image to be displayed is stored in a suitable storage means which can be referred to as the "image" buffer portion of memory. Once all of the data required to define the image is so stored, the image information can then be transferred to a local display processor where it is placed into a conventional frame buffer means so that the image is then displayed on the raster display screen on a line-by-line basis.
A major disadvantage of such an approach is that the entire image must be created and stored at the host processor before any data concerning the points which define the image can be supplied to the display processor. It is entirely impractical in such a system to attempt to transfer such information from the host processor to the display processor incrementally as image data for each point is created. The overall time for such a process would be too long for any practical advantage to be obtained from such a process. Accordingly, no matter what hidden surface, or depth buffer, algorithm is used by the host processor to provide the desired depth relationship data, the need for storing all the image information at the host processor permits the image to be displayed only when all such information is created and made available at the host. Normally, then, the most effective way to display the information is on a conventional line-by-line basis from top to bottom of a display screen.
Accordingly, once the user wishes to use the information in the data base to display an image, the user must wait for data defining the complete image to be duplicated in a non-displayable form at the host processor before it can be transferred to the display processor and the image begins to appear on the display screen. Moreover, when a change is made in the image by the user, the change must be created at the appropriate locations by the host processor and the entire image must be re-displayed on a scanned line-by-line basis before the revised image can be seen by the user. Nor can an overall image comprising several distinct objects be presented to the user on the display screen on an object by object basis.
Such a system effectively acts in the nature of a raster plotting device rather than a random access display device and requires a relatively long waiting time from the time a request for an image display is made and the time the first line of the image can even begin to be displayed on the screen. Once such display begins, the host processor must supply every data point from the image buffer at the host processor to the frame buffer of the display processor, a significant burden.
In order to improve the operation of such a system, it is desirable to devise a system which avoids the relatively long waiting time required before a user-requested image can be created and displayed. It is further desirable for such an improved system to permit a change at any location of the image without requiring the host processor to re-calculate the entire image that is going to be displayed before such change can be seen at the display screen.
Moreover, it is desirable for a system to permit a "build-up" of the overall image so that various locations of the image can be displayed independently of other locations thereof and the display of the overall image can be continuously built up in any selected order of its component parts or objects. The build up of an overall image in a selected order can be generally referred to as an incremental construction of the overall image.